package heyuanyuan;
import java.util.Scanner;

public class LinkedListSolution {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入链表1
        System.out.print("请输入 链表1 的结点个数:");
        ListNode list1 = inputList(scanner, "链表1");

        // 输入链表2
        System.out.print("请输入 链表2 的结点个数:");
        ListNode list2 = inputList(scanner, "链表2");

        // 打印原始链表
        System.out.println("\n链表1：" + formatList(list1));
        System.out.println("链表2：" + formatList(list2));

        // 合并链表
        ListNode merged = mergeLists(list1, list2);
        System.out.println("\n合并链表1和链表2：" + formatList(merged));

        // 逆序输出
        System.out.println("合并链表1和链表2并将其逆序：" + formatReverseList(merged));
    }

    // 输入链表数据
    private static ListNode inputList(Scanner scanner, String listName) {
        int n = scanner.nextInt();
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

        for (int i = 0; i < n; i++) {
            System.out.printf("请输入 %s 的第 %d 个结点的值:", listName, i + 1);
            current.next = new ListNode(scanner.nextInt());
            current = current.next;
        }

        return dummy.next;
    }

    // 合并两个有序链表
    private static ListNode mergeLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    // 格式化链表输出
    private static String formatList(ListNode head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val);
            if (head.next != null) sb.append("->");
            head = head.next;
        }
        return sb.append("->null").toString();
    }

    // 格式化逆序链表输出
    private static String formatReverseList(ListNode head) {
        StringBuilder sb = new StringBuilder();
        printReverseHelper(head, sb);
        return sb.append("->null").toString();
    }

    // 递归辅助逆序输出
    private static void printReverseHelper(ListNode node, StringBuilder sb) {
        if (node == null) return;
        printReverseHelper(node.next, sb);
        sb.append(node.val);
        if (node.val != getFirstVal(node)) sb.append("->");
    }

    // 获取链表第一个节点的值
    private static int getFirstVal(ListNode node) {
        while (node.next != null) node = node.next;
        return node.val;
    }
}